package com.cqs.leetcode.graph;

import com.cqs.leetcode.Ints2AndInt;
import com.cqs.leetcode.ds.ArraysUtils;

import java.util.*;

/**
 * lixw
 * 2021/11/8
 **/
public class CourseScheduleII210 {

    //数据结构: 入度数组 + 队列【入度为0的边的起点】 + 访问多的状态
    //访问一个点的时候， 删除这个点为起点的边， 且修改入度数组，若新产生的入度为0的顶点要加入
    //队列为空的时候 要是还有顶点没有访问过 那么存在环
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        //入度
        int[] inDu = new int[numCourses];
        //边的另外一个端点
        Map<Integer, List<Integer>> edges = new HashMap<>();
        for (int[] pre : prerequisites) {
            inDu[pre[1]]++;
            List<Integer> ints = edges.getOrDefault(pre[0], new ArrayList<>());
            ints.add(pre[1]);
            edges.put(pre[0], ints);
        }

        Queue<Integer> q = new ArrayDeque<>();

        for (int i = 0; i < inDu.length; i++) {
            if (inDu[i] == 0) {
                q.add(i);
            }
        }
        int[] result = new int[numCourses];
        boolean[] visited = new boolean[numCourses];
        int visitNum = numCourses;
        while (q.size() > 0) {
            Integer poll = q.poll();
            visited[poll] = true;
            result[--visitNum] = poll; //保存访问结果
            List<Integer> edgeList = edges.getOrDefault(poll, new ArrayList<>());
            for (Integer edgePoint : edgeList) {
                //新产生的入度为0的点，没有访问过的 加入队列
                if (--inDu[edgePoint] == 0 && !visited[edgePoint]) {
                    q.add(edgePoint);
                }
            }
        }

        return visitNum == 0 ? result : new int[]{};
    }


    public static void main(String[] args) {
        CourseScheduleII210 c = new CourseScheduleII210();
        List<Ints2AndInt> cases = new ArrayList<>();
        cases.add(new Ints2AndInt(new int[][]{{1, 0}}, 2));
        cases.add(new Ints2AndInt(new int[][]{}, 2));
        for (Ints2AndInt t : cases) {
            System.out.println(t + "----> " + ArraysUtils.formatInts(c.findOrder(t.target, t.arr)));
        }


    }


}
